(* Dynamic array *)
type 'a dynArray = {
                    mutable size : int;
                    mutable maxCapacity : int;
                    mutable a : 'a array}

(* next_power_of_two
 * Return the power of two immediately geater than n.
 * Inputs:
       n as int : base number.
 * Output:
       val as int : next power of two.
 *)
let next_power_of_two n =
    let i = ref 1 in
       while !i < n do
          i:=!i*2
       done;
       !i

(* make
 * Create a new dynamic list.
 * Inputs:
      n as int : initial size.
      init as 'a : initial value of the dynamic array.
 *)
let make n init =
   let n2 = next_power_of_two n in
     { size=n; maxCapacity=n2;a=Array.make n2 init }

(* get
 * Returns the i-th element a the list a.
 *)
let get a i =
   a.a.(i)

(* set
 * Sets the n-th element of the dynamic array a
 *)
let set a v i =
   a.a.(i) <- v

(* size
 * Returns the size of the array a.
 *)
let size a =
   a.size

(* add
 * add the element v at the end of the dynamic array a.
 *)
let add a v =
      if a.size = a.maxCapacity then
        let nm = a.maxCapacity * 2 in
        let na = Array.make nm v in
           begin
           for i=0 to a.size-1 do
              na.(i) <- a.a.(i)
           done;
           a.maxCapacity <- nm;
           a.a <- na;
           a.size <- a.size+1;
           end
      else
         begin
         a.a.(a.size) <- v;
         a.size <- a.size+1;
         end
